package leetcode.D1000.T931;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-20 20:58:22 星期日
 */

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        if (m == 1)
            return matrix[0][0];
        int[] dp = new int[m];
        for(int i=0; i<m; ++i) {
            int last = dp[0];
            for(int j = 0; j<m; ++j) {
                if (j == 0) {
                    dp[j] = Math.min(dp[j], dp[j+1]) + matrix[i][j];
                } else if (j == m-1) {
                    dp[j] = Math.min(dp[j], last) + matrix[i][j];
                } else {
                    int t = Math.min(last, Math.min(dp[j], dp[j+1])) + matrix[i][j];
                    last = dp[j];
                    dp[j] = t;
                }
            }
        }
        int result = Integer.MAX_VALUE;
        for(int i=0; i<m; ++i) {
            result = Math.min(result, dp[i]);
        }
        return result;
    }
}
